﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace NextGreaterElement
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input1 = new int[] { 4, 5, 2, 25, 20, 11, 13, 21, 3 };
            NextGreater(input1);

            int[] input2 = new int[] { 2, 25, 20, 11, 21, 3 };
            NextGreaterUsingStacks(input1);
            Console.Read();
        }

        public static void NextGreater(int[] input)
        {
            int loops = 0;
            int comparisions = 0;

            for (int i = 0; i < input.Length; i++)
            {
                int max = -1;
                loops++;

                for (int j = i + 1; j < input.Length; j++)
                {
                    loops++;

                    if (input[j] > input[i] && input[j] > max)
                    {
                        comparisions++;

                        max = input[j];
                        break;
                    }
                }

                Console.WriteLine("Current {0} - Next Greater Value {1}", input[i], max);                
            }

            Console.WriteLine("Loops {0} - Comparisions {1}", loops, comparisions);
            Console.WriteLine();
        }

        public static void NextGreaterUsingStacks(int[] input)
        {
            int loops = 0;
            int comparisions = 0;

            Stack<int> s = new Stack<int>();

            for (int i = 0; i < input.Length;)
            {
                loops++;
                comparisions++;

                if (s.Count == 0)
                {
                    s.Push(input[i]);
                    i++;
                }
                else
                {
                    comparisions++;

                    int current = s.Pop();

                    if (current < input[i])
                    {
                        Console.WriteLine("Current {0} - Next Greater Value {1}", current, input[i]);
                    }
                    else
                    {
                        s.Push(current);
                        s.Push(input[i]);
                        i++;
                    }
                }              
            }

            while (s.Count() > 0)
            {
                Console.WriteLine("Current {0} - Next Greater Value {1}", s.Pop(), -1);
            }

            Console.WriteLine("Loops {0} - Comparisions {1}", loops, comparisions);
            Console.WriteLine();
        }

    }
}
